О перечислении максимальных бесконечно-порожденных классов 01-функций трехзначной логики 

Сергей Серафимович Марченков, доктор физико-математических наук, профессор, профессор кафедры математической кибернетики, Московский государственный университет имени М. В. Ломоносова (Россия г. Москва, Ленинские горы, 1), ssmarchen@yandex.ru

519.716 

DOI

10.21685/2072-3040-2021-3-1

Актуальность и цели. Операция суперпозиции является основной операцией при исследовании функций многозначной логики. На базе этой операции определяются классификации функций многозначной логики, позволяющие решать важные проблемы выразимости и полноты. Однако если для булевых функций (функций двузначной логики) эти проблемы давно решены, то, например, для функций k-значной логики (при k ≥ 3 ) проблема описания всех замкнутых классов, повидимому, не может иметь удовлетворительного решения – в этом случае число замкнутых классов континуально. В связи с этим исследования по замкнутым (относительно операции суперпозиции) классам функций k-значной логики развиваются в направлении описания различных фрагментов решетки замкнутых классов: максимальных и минимальных классов, верхних и нижних конусов, конечных и счетных интервалов, определяемых содержательно интересными классами, и т.п. Одна из задач данного направления, поставленная С. В. Яблонским в начале 1980-х гг., – описать все максимальные бесконечно-порожденные классы решетки замкнутых классов. В 1986 г. Е. А. Михеева и Г. Тардош нашли примеры таких максимальных классов: Е. А. Михеева – при любом k ≥ 3 , Г. Тардош – при k = 8 . Идеи Тардоша в дальнейшем развивала О. С. Дудакова. Вместе с тем при фиксированных k определить серии максимальных бесконечно-порожденных классов пока не удалось. В 2019 г. автор опубликовал статью, где в трехзначной логике определены 4 максимальных бесконечно-порожденных класса Π1 −Π4 , которые состоят из функций, принимающих лишь значения 0 и 1 (такие же классы можно определить для функций, принимающих значения 0,2 и 1,2). Таким образом, появилась серия из 12 максимальных бесконечно-порожденных классов. Есть все основания полагать, что классами Π1 −Π4 исчерпываются все максимальные бесконечно-порожденные классы 01-функций. Доказать этот факт можно по следующей схеме. Сначала для каждого класса Πi следует определить все «простейшие» функции от двух или трех переменных, которые получаются суперпозициями из произвольной функции, не принадлежащей классу Πi . Затем необходимо перебрать всевозможные четверки «простейших» функций и с использованием известных достаточных условий конечной порождаемости установить конечную порождаемость замкнутых классов, содержащих
выбранные четверки функций. Материалы и методы. В построениях и доказательствах используются методы теории функциональных систем. Результаты и выводы. Рассматривается класс Π -функций трехзначной логики, принимающих только значения 0 и 1. В классе Π определены 4 бесконечно-порожденных класса Π1 −Π4 , которые обладают свойством максимальности: всякий замкнутый класс из Π, собственным образом содержащий любой из классов Π1 −Π4 , является конечнопорожденным. Для каждого класса Πi и произвольной функции f , не принадлежащей Πi и существенно зависящей не менее чем от двух переменных, определяются все «простейшие» функции от двух или трех переменных, которые получаются суперпозициями функции f и которые не входят в класс Πi . В дальнейшем все эти функции предполагается использовать для доказательства того, что в классе Πi все максимальные бесконечно-порожденные классы исчерпываются классами Π1 −Π4 . Подобное доказательство ориентировочно должно заключаться в анализе нескольких тысяч четверок, состоящих из полученных «простейших» функций. 

Ключевые слова

бесконечно-порожденные классы, 01-функции трехзначной логики, теория функциональных систем

 Скачать статью в формате PDF

1. Post E. L. Introduction to a general theory of elementary propositions // Amer. J. Math. 1921. Vol. 43, № 4. P. 163–185.
2. Post E. L. Two-valued iterative systems of mathematical logic // Annals of Math. Studies. 1941. Vol. 5. P. 1–122.
3. Марченков С. С. Замкнутые классы булевых функций. М. : Физматлит, 2000. 126 с.
4. Марченков С. С. Основы теории булевых функций. М. : Физматлит, 2014. 135 с.
5. Янов Ю. И., Мучник А. А. О существовании k -значных замкнутых классов, не имеющих базиса // Доклады Академии наук СССР. 1959. Т. 127, № 1. С. 44–46.
6. Михеева Е. А. О существовании в k -значной логике максимальных классов, не имеющих конечного базиса // Доклады Академии наук СССР. 1986. Т. 287, № 1. С. 49–52.
7. Михеева Е. А. Построение в Pk максимальных классов, не имеющих конечных базисов // Дискретная математика. 1998. Т. 10, № 2. C. 137–159.
8. Tardos G. A not finitely generated clone of monotone operations // Order. 1986. Vol. 3. P. 211–218.
9. Дудакова О. С. Об одном семействе предполных классов функций k -значной логики, не имеющих конечного базиса // Вестник Московского университета.
Серия 1: Математика. Механика. 2006. № 2. С. 29–32.
10. Марченков С. С. Конечно- и бесконечно-порожденные классы 01-функций трехзначной логики // Математические вопросы кибернетики. 2019. №. 19.
С. 21–36.